package algorithm;

/**
 * @author apple
 * @Classname PrintBinaryTree
 * @Description 输出二叉树结构
 * 需要BinaryTree.java
 * @Date 2020/3/2 9:54
 */
public class PrintBinaryTree {
    public static void main(String[] args) {
        PrintBinaryTree printBinaryTree = new PrintBinaryTree();
        printBinaryTree.binaryTreePrint();
    }

    public void binaryTreePrint() {
        BinaryTree binaryTree = new BinaryTree();
        /**构造二叉树**/
        int[] list = {10, 25, 13, 1, 6, 11, 15};

        binaryTree=binaryTree.insertTreeNodeByInt(binaryTree,list);

        /**树的高度 **/
        int treeHeight = binaryTree.height(binaryTree.getRoot());
        System.out.println("树的高度=" + treeHeight);

        /** 用一个字符串数组来存储每个位置应显示的元素
         *  二维字符串数组,一个是(树的高度*2)-1，一个是树最后一行的宽度=2的（n - 1）次方乘3，再加1
         *  **/
        int height = treeHeight * 2 - 1;
        int width = (2 << (treeHeight - 2)) * 3 + 1;
        String treeStrings[][] = new String[height][width];
        /**初始化字符串数组 **/
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                treeStrings[i][j] = " ";
            }
        }
        /** 从根节点开始，递归处理整个树 **/
        writeArray(binaryTree.getRoot(), 0, width / 2, treeStrings, treeHeight);
        printStrings(treeStrings);
    }

    /**
     * 递归分解二叉树
     * currentNode:当前节点
     * height:字符串数组的层数(第几层)
     * width：字符串数组的宽度(第几个)
     * treeStrings: 字符串数组
     * treeHeight: 二叉树的高度
     **/
    private void writeArray(TreeNode currentNode, int heightIndex, int widthIndex, String[][] treeStrings, int treeHeight) {
        /** 保证输入的树不为空**/
        if (currentNode == null) {
            return;
        }
        /**将当前节点保存到数组中,注意数据类型转换**/
        treeStrings[heightIndex][widthIndex] = String.valueOf(currentNode.getValue());

        /** 计算当前位于树的第几层**/
        int currLevel = ((heightIndex + 1) / 2);
        /**当到了最后一层，则返回**/
        if (currLevel == treeHeight) {
            return;
        }
        /** 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）**/
        int gap = treeHeight - currLevel - 1;
        /** 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值 **/
        if (currentNode.leftTreeNode != null) {
            treeStrings[heightIndex + 1][widthIndex - gap] = "/";
            writeArray(currentNode.leftTreeNode, heightIndex + 2, widthIndex - gap * 2, treeStrings, treeHeight);
        }
        if (currentNode.rightTreeNode != null) {
            treeStrings[heightIndex + 1][widthIndex + gap] = "\\";
            writeArray(currentNode.rightTreeNode, heightIndex + 2, widthIndex + gap * 2, treeStrings, treeHeight);
        }
    }

    private void printStrings(String[][] treeStrings) {
        for (String[] line : treeStrings) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}